package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * @author: lynn
 * @Descript: 数组中出现次数超过一半的数
 * @date: 2021/3/14 0:47
 * @version: 1.0
 */
public class Q28_MoreThanHalfNum {
    public static void main(String[] args) {
        //int[] a={1,2,3,2,4,2,5,2,3};
        int[] a={1,2,3,2,2,2,5,4,2};
        //set 与list的转换
        System.out.println(""+doFind(a));

    }
    public static int doFind(int[] a){
        int result=0;
        if(a==null||a.length==0){
            return result;
        }
        if (a.length==1){
            return a[0];
        }
        Map<Integer,Integer> dataMap=new HashMap<>();
        for (int i=0;i<a.length;i++){
            if (dataMap.get(a[i])==null){
                dataMap.put(a[i],1);
            }else {
                dataMap.put(a[i],dataMap.get(a[i])+1);
                if (dataMap.get(a[i])>(a.length>>1)){
                    result=a[i];
                    break;
                }
            }
        }
        return result;
    }
}
